package com.company.algo.listnode;

import com.company.algo.pojo.ListNode;

/**【用快速排序来排单向链表】
 1. 找pivot->左边第一个
 2. i,j位置都为pivot后一个
 3. 移动两个指针，保证
     - i左边的数<pivot
     - 让[i,j)>pivot
     3.1 如果 nums[j]>pivot->j++
     3.2 如果 nums[j]<pivot,
         3.2.1 交换i,j
         3.2.2 i++,j++
 4. 当j为null时(移出nums)，交换i-1和pivot
 至此就确定了一个pivot的所在位置，然后递归即可
 */
public class QuickSortList {
    public void quickSort2(int[] arr){
        subSort(arr,0,arr.length-1);
    }
    private void subSort(int[] arr, int low, int high) {
        if (low<high){
            int pivot = arr[low];
            int i = low+1;
            int j = low+1;
            while (j<=high){
                //一开始i,j同步一直到第一个比pivot大的数出现，i停下了
                if (arr[j] < pivot){
                    swap(arr,i,j);
                    i++;
                }
                j++;
            }
            //最后交换 pivot 和 第 i-1 个元素
            swap(arr,low,i-1);
            //递归调用左右两边
            subSort(arr,low,i-2);
            subSort(arr,i,high);
        }

    }

    public ListNode sortList(ListNode head) {
        ListNode cur = head;
        while (cur.next!=null) cur = cur.next;
        quickSortNodes(head,cur);
        return head;
    }

    private void quickSortNodes(ListNode low, ListNode high) {
        if (low == null || low.next == null || low == high) return;
        int pivot = low.val;
        ListNode i_pre = low;
        ListNode i = low.next;
        ListNode j = low.next;
        while (j!=high.next){
            if (j.val < pivot){
                swapNode(i,j);
                i_pre = i;
                i = i.next;
            }
            j = j.next;
        }
        swapNode(low,i_pre);
        quickSortNodes(low,i_pre);
        quickSortNodes(i,high);
    }

    private void swapNode(ListNode i, ListNode j) {
        int t = i.val;
        i.val = j.val;
        j.val = t;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
